// Created by wxx on 2021/10/21 21:12
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {

        int n = nums.size();

        // (1) 让所有在1~n中的数据t放置到nums[t - 1]中
        for (int i = 0; i < n; i++) {
            int &t = nums[i];  // t应该放到nums[t - 1]的位置
            while (t > 0 && t <= n && nums[t - 1] != t)
                swap(t, nums[t - 1]);  // 此时下标为t-1的位置正确放置了t, 但是nums[i]换过来的数据不一定是i+1, 因此是while
        }

        // (2) 找出不满足nums[i] == i+1的位置，返回i+1; 如果都满足，返回n+1
        for (int i = 0; i < n; i++)
            if (nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }
};

int main() {

    vector<int> nums = {3, 4, -1, 1};
    cout << Solution().firstMissingPositive(nums) << endl;

    return 0;
}
